package test;


import niuke.TreeNode;

/**
 * description:
 * author:zt
 * date:2021-08-24
 */

/**
 * 二叉树权值最大的叶子节点到权值最小的叶子节点的距离
 * 有一棵二叉树，树上每个点标有权值，权值各不相同，请设计一个算法算出权值最大的叶节点到权值最小的叶节点的距离。
 * 二叉树每条边的距离为1，一个节点经过多少条边到达另一个节点为这两个节点之间的距离。 给定二叉树的根节点root，请返回所求距离。
 */
public class Tree {
    public static void main(String[] args) {
        System.out.println("hello");
        TreeNode root4 = new TreeNode(4);
        TreeNode root2 = new TreeNode(2);
        TreeNode root3 = new TreeNode(3);
        TreeNode root5 = new TreeNode(5);
        TreeNode root1 = new TreeNode(1);
        root4.left = root2; root4.right = root3;
        root2.left = root1; root1.right = root5;
        Tree ma = new Tree();
        System.out.println(ma.getDis(root4));
        System.out.println("111");
        System.out.println("222");
    }
    private TreeNode maxNode = new TreeNode(Integer.MIN_VALUE);
    private TreeNode minNode = new TreeNode(Integer.MAX_VALUE);
    private boolean stop = false;
    public int getDis(TreeNode root) {
        // write code here
        if (root==null) return 0;
        getMaxAndMin(root);
        return getMaxLength(root);
    }
    public void getMaxAndMin(TreeNode root){
        if (root==null) return;
        if (root.left==null && root.right==null){
            if (root.val < minNode.val) minNode = root;
            if (root.val > maxNode.val) maxNode = root;
        }
        getMaxAndMin(root.left);
        getMaxAndMin(root.right);
    }
    public int getMaxLength(TreeNode root){
        if (root==null) return -1;
        if (root==maxNode) return 1;
        if (root==minNode) return 1;

        int left = getMaxLength(root.left);
        int right = getMaxLength(root.right);
        if (stop){
            return left!=-1?left:right;
        }
        if (left!=-1 && right==-1) return left+1;
        else if (left==-1 && right!=-1) return right+1;
        else if (left!=-1 && right!=-1){
            stop = true;
            return left+right;
        }
        else return -1;
    }
}
